What's a Queue?

	List restricted to remove only at front and add only at back
	FIFO


How is a Queue similar to, but also different from, a Stack?

	both Queues and Stacks are restricted Lists
	but Stack restricts both add and remove only at top


What are some examples where Queues are used?

	waiting in line
	print queue for shared printer
	request queue for web server


What are the operations on a Queue?

	enqueue
	dequeue
	Queue operations are constant time


Queue interface

public interface Queue {
	void enqueue (Object x);
	Object dequeue ();
	Object getFront();
	boolean isEmpty();
	void clear();
	int size();
}


There is no Queue interface or Queue class in the java library.
Can you implement a Queue using some other class?

	LinkedList
	enqueue() is addLast()
	dequeue() is removeFirst()
	getFront() is getFirst()


What kinds of applications is a Queue good for?

	fair service


DEMO	(Emergency Room)



What's a Priority Queue?

	each item in the queue is assigned a priority
	item with highest priority is next out


What are some examples where Priority Queues are used?

	fairness based on arrival time may not be most efficient
	size of a request may affect its service time


What are the operations on a Priority Queue?

	insert
	deleteMin


Priority Queue interface

public interface PriorityQueue {
	void insert (Object x);
	Object findMin();
	Object deleteMin();
	boolean isEmpty();
	void clear();
	int size();
}


There is no Priority Queue interface or class in the java library.
Can you implement a Priority Queue using some other class?

	SortedSet (almost works)
	only works with no duplicate priorities
	insert() is add()
	findMin() is first()
	deleteMin() is first() and remove()


What kinds of applications is a Priority Queue good for?

	simulation


DEMO	(Emergency Room with priorities)